Zgadywanka
Limit pamięci: 32 MB
Bajtazar gra z Bajtonim w następującą grę. Bajtoni losuje sobie ciąg składający
się z 0 i 1 o długości
cyfr. Zadaniem Bajtazara jest
odgadnięcie ciągu, który wylosował Bajtoni. W tym celu może zadawać pytania
typu: "Czy suma wyrazów ciągu od
-tego do
-tego jest parzysta?".
Bajtoni chętnie udzielał odpowiedzi, jednak po pewnym czasie Bajtazar zaczął
podejrzewać, że jego kolega oszukuje. Chciałby sprawdzić kiedy Bajtoni udzielił
pierwszej odpowiedzi sprzecznej z poprzednimi, dlatego zwrócił się do Ciebie o
pomoc.
Zadanie
Napisz program, który:
- wczyta opis pytań zadawanych przez Bajtazara oraz odpowiedzi Bajtoniego,
- obliczy największe takie
, dla którego odpowiedzi Bajtoniego na pierwszych
pytań są niesprzeczne,
- wypisze wynik na standardowe wyjcie.
Wejście
W pierwszym wierszu standardowego wejścia znajduje się jedna
liczba całkowita
(
), oznaczajca liczbę pytań
Bajtazara. Każdy z kolejnych
wierszy zawiera opis jednego pytania Bajtazara
oraz odpowiedzi Bajtoniego w postaci trzech liczb całkowitych
,
i
(
). Liczy
i
oznaczają, że Bajtazar zapytał o sumę wyrazów ciągu od
-tego do
-tego
włącznie. Jeśli
, to Bajtoni odpowiedział, że suma ta jest parzysta.
Jeśli
, Bajtoni powiedział, że suma jest nieparzysta.
Wyjście
Twój program powinien wypisać w pierwszym i jedynym wierszu standardowego
wyjścia jedną liczbę całkowitą - największe takie
, dla którego odpowiedzi
Bajtoniego na pierwszych
pytań są niesprzeczne.
Przykład
Dla danych wejściowych:
5
3 3 0
2 5 1
1 4 0
2 5 0
1 5 1
poprawną odpowiedzią jest:
3
Autor zadania: Jakub Łącki (zapożyczenie).